package leetcode.editor.vscdev.backtracking;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/* 给定一个候选人编号的集合 candidates 和一个目标数 target ，
 * 找出 candidates 中所有可以使数字和为 target 的组合。
 * candidates 中的每个数字在每个组合中只能使用 一次 。
 * 注意：解集不能包含重复的组合。  */
public class lc40 {
    class Solution {
        List<List<Integer>> result = new ArrayList<>(); // 结果
        List<Integer> path = new ArrayList<>(); // 路径
        int sum = 0; // 总和
        public List<List<Integer>> combinationSum2(int[] candidates, int target) {
            // 进行排序,将重复数字放到一起.
            Arrays.sort(candidates);
            backtracking(candidates, target, 0);
            return result;
        }
        public void backtracking(int[] candidates, int target, int start) {
            // 终止条件
            if (sum == target) {
                result.add(new ArrayList<>(path));
                return;
            }
            // 过程处理
            for (int i = start; i < candidates.length; i++) {
                // 剪枝
                if (sum + candidates[i] > target)
                    break;
                // 去重,要对同一树层使用过的元素进行跳过
                if (i > start && candidates[i] == candidates[i - 1]) {
                    continue;
                }
                sum += candidates[i];
                path.add(candidates[i]);
                backtracking(candidates, target, i+1);
                sum -= candidates[i];
                path.removeLast();
            }
        }
    }
}
